1. Field of the Invention
The invention relates to a digital root extraction circuit for determining the square root of a 2n-bit binary number, the bit significance thereof decreasing from the first to the 2n.sup.th bit, which circuit comprises a logic array of controllable add/subtract cells (CAS cells) each of which comprises a first and a second data input, a control input, a carry signal input, a carry signal output and a sum signal output. The root extraction circuit comprises n sub-circuits, an m.sup.th sub-circuit thereof comprising m+1 CAS cells, where 1.ltoreq.m.ltoreq.n. The carry signal output of a CAS cell for the processing of bit signals of a given significance is connected to the carry signal input of a CAS cell for the processing of bit signals of a next higher significance, the carry signal output of the first CAS cell in any m.sup.th sub-circuit forming an m.sup.th output of the root extraction circuit for an output bit having a significance m. A first data input of the (m-i).sup.th CAS cell in the m.sup.th sub-circuit is connected to the (m-i).sup.th output of the root extraction circuit, where 1.ltoreq.i.ltoreq.m, a second data input of such (m-i).sup.th CAS cell being connected to the sum signal output of the m.sup.th CAS cell in the (m-1).sup.th sub-circuit. The control input of at least the CAS cells in an m.sup.th sub-circuit whose first data inputs are connected to a sum signal output of a CAS cell of an (m-1).sup.th sub-circuit, are connected to the (m-1).sup.th output of the root extraction circuit. The m.sup.th and m+1.sup.th CAS cells of an m.sup.th sub-circuit receive bit signals having a significance 2m-1 and 2m, respectively, on their first data input, the control input of the m+1.sup.th CAS cell being connected to its carry signal input.
1. Description of the Related Art
A root extraction circuit of this kind is known from the book "Computer Arithmetic: Principles, Architecture and Design", by Kai Hwang, published by John Wiley & Sons. The root extraction circuit is shown and described in chapter 11, section 2, pages 360-2 (FIG. 11.2), and is realised by means of so-called controllable add/subtract cells (CAS cells) which are shown (FIG. 2.10) and described in the same book in chapter 2, section 3, pages 42-3. The construction of the root extraction circuit is based on an algorithm which is described on said pages 360-2; according to this algorithm, signals must be inverted in some locations in the root extraction circuit before they can be applied to a CAS cell. However, the inverter circuits required for inverting the signals disturb the regular pattern of the CAS cells which would be feasible if only CAS cells were integrated. The fact that the inverter circuits are required and that they disturb a feasible regular pattern for integration is found to be very disadvantageous.